Currently there are various broadcast schemes called “Broadcast Encryption Scheme” (BES) making it possible to broadcast data in a reliable manner. The principle of a BES is as follows. Each user u has a specific set I(u) containing several encryption keys called KEKs (“Key Encryption Keys”). At each session, the data are encrypted with a “session key”, and the session key (and if necessary new KEKs keys) is encrypted with the KEKs keys such that each authorized user knows at least one of the keys used and the unauthorized (or “denied”) users do not know any of the keys used.
The choice of the BES broadcast method determines the KEKs keys, their structure, the possibility of renewal and the choice of the KEKs keys used for the encryption for a given session.
To find a truly effective encryption when the data item is transmitted via a medium with very small bandwidth and when there are several possible “denied” users is a problem. The choice of the BES broadcast scheme may be critical, for example, if the data item is transmitted via satellites.
The prior art discloses several encryption schemes for the broadcasting of data, in particular two large types of schemes, the “stateless” schemes and the “stateful” schemes described below.
In a “stateless” scheme, all the KEKs encryption keys are distributed when the system is initialized. The KEKs keys are then static throughout the lifetime of the system and no other key is added. Only the session key may be changed. This means that, when a user loses the connection or that, for other reasons, he lacks the data packets using the KEKs keys, he cannot decrypt the payload content of the message (not knowing the current session key), but, when he has access to the next packets using KEKs keys, he will be able to retrieve the future keys of the session with no additional effort.
In a “stateful” scheme, the KEKs encryption keys may be updated or added thanks to key management messages. This means that, if the user lacks the key management packets, it may be impossible for him to decrypt the following session keys. Since it is possible for the users to lose data packets, a “stateful” scheme must be supplemented by a packet-retrieval mechanism. Usually, a “stateful” scheme may always be converted into a “stateless” scheme by including all the previous messages in each new message.
Characteristic:Is each sessionindependent of the stateMainMainof the previous session?advantagedisadvantages“Stateless”YESA user may beThe size of theschemeEach session contains alldisconnectedmessagethe information from thefrom a stationpotentiallypastwithout losingincreases with(denied users, newthe usefuleach sessionusers, etc.)information forthe next session“Stateful”NO.The size of theIf a user isschemeEach session containsmessage doesdisconnectedonly the usefulnot in principleduring a session,information that is newincrease fromhe may lose thecompared to the pastone session tousefulthe next sessioninformationfor the futuresessionsThe most recent articles relating to a BES broadcast scheme use two main types of structure of KEKs encryption keys.KEKs Structure No 1:
The first encryption key structure is a simple hierarchical tree. The users are represented by leaves of a tree T. This tree is not necessarily binary or balanced.
Each node vi of the tree is associated with a key ki. The leaves are considered to be particular nodes. The keys ki are KEKs keys used in a BES. During initialization, each user u (that is to say each leaf u) receives the set of all the keys ki corresponding to the nodes vi belonging to the shortest path between the root of T and the leaf u. Therefore the key ki is distributed to each leaf of the subtree Si whose root is the node vi and only to these leaves. Any data item encrypted with the key ki is sent to the leaves of Si and only to these leaves. The root key is marked k0 (that is to say the key associated with the root v0 of the tree T) and the set of all the keys ki is marked {ki}.
KEKs Structure No 2:
The second KEKs encryption key structure is also based on a hierarchical tree T such that each user is represented by a tree leaf. The tree is binary and a key ki,j is associated with a difference of subsets
Si,j=Si−Sj such that the subtree Si contains the subtree Sj.
Each key ki,j is distributed for each leaf belonging to the subset Si,j, (that is to say belonging to Si but not to Sj) and this key is used to encrypt any data item intended for all the users belonging to Si,j and only to them.
A key k0, - - - is associated with the whole of the tree T and given to each of the users. {ki,j} is used to indicate the set of all the keys ki,j including the key k0, - - -.
Many BES broadcast methods, “stateful” or “stateless”, use the KEKs No 1 structure as, for example, the CS method described in reference [3] or LKH described in one of the references [6], [5], [4-RFC-2627]. Several effective BES stateless methods use the KEKs No 2 structure, such as the “subset difference method” SD given in [3] or schemes derived from SD.
The prior art shows that the No 1 key structure is adapted to the “stateful BESs” scheme while the No 2 structure is better adapted to the “stateless BESs” scheme.
The authors in reference [1] propose two hybrid schemes which combine a “stateful” algorithm and a “stateless” algorithm, having the same KEKs key structure.
Hybrid Scheme Based on the Foregoing Schemes
A simple hybrid scheme mixes the CS “stateless” method described, for example, in reference [3] and the LKH “stateful” method (see references [6], [5], [RFC-2627]). If the CS method only is used to broadcast a message and if the number of “denied” users becomes very large, then the size of the broadcast session becomes very large. The main idea of the hybrid scheme described in [1] is as follows: usually, the CS stateless method is used, but when the number of denied users is greater than a fixed threshold, then the LKH stateful method is used to renew the keys known by the authorized users and the denied users. Therefore the set of the denied users is updated and the CS method is used again. The bandwidth used is therefore improved relative to that obtained when only the CS method is used.
The hybrid schemes described in the prior art however do not propose a solution making it possible to mix schemes each having different KEKs encryption key structures.
The idea of the present invention is based on a new hybrid scheme mixing a “stateless” procedure A1 and a “stateful” procedure A2 using various key structures.